package com.future;

import java.util.ArrayList;
import java.util.List;

/**
 * Description: 152. 乘积最大子数组
 *
 * @author weiruibai.vendor
 * Date: 2022/11/7 17:29
 */
public class Solution_152 {

    public static void main(String[] args) {

        Solution_152 instance = new Solution_152();

        int[] nums = new int[]{3, -6, 0, 32, 0, -6, -5, 2, 1, 0};
        nums = new int[]{2, 3, -2, 4};
        nums = new int[]{-2, 0, -1};
        nums = new int[]{3, -1, 4};
        nums = new int[]{2, -5, -2, -4, 3};
        System.out.println(instance.maxProduct(nums));
    }

    /**
     * {2, -5, -2, -4, 3}
     * <p>
     * hashNegative
     * {2 -5 20}
     * dp
     * {2}
     *
     * @param nums
     * @return
     */
    public int maxProduct(int[] nums) {
        int N = nums.length;
        if (N == 1) {
            return nums[0];
        }
        int dp[] = new int[N];
        int[] hasNegativeDp = new int[N];
        dp[0] = nums[0];
        hasNegativeDp[0] = nums[0];
        for (int i = 1; i < N; i++) {
            int val;
            int hasNegative;
            if (nums[i] == 0) {
                val = 0;
                hasNegative = 0;
            } else if (nums[i] < 0) {
                hasNegative = nums[i];
                val = nums[i];
                if (hasNegativeDp[i - 1] != 0) {
                    hasNegative = hasNegativeDp[i - 1] * hasNegative;
                }
            } else {
                // > 0
                hasNegative = nums[i];
                val = nums[i];
                if (hasNegativeDp[i - 1] != 0) {
                    hasNegative = hasNegativeDp[i - 1] * hasNegative;
                }
                if (dp[i - 1] > 0) {
                    val = dp[i - 1] * val;
                }
            }
            dp[i] = val;
            hasNegativeDp[i] = hasNegative;

        }
        int ans = dp[0];
        for (int i = 1; i < N; i++) {
            ans = Math.max(ans, Math.max(dp[i], hasNegativeDp[i]));
        }
        return ans;
    }
}
